1570. Dot Product of Two Sparse Vectors
Medium

Given two sparse vectors, compute their dot product.

Implement class SparseVector:

  • SparseVector(nums) Initializes the object with the vector nums
  • dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Follow up: What if only one of the vectors is sparse?

 

Example 1:

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8

Example 2:

Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0

Example 3:

Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6

 

Constraints:

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • 0 <= nums1[i], nums2[i] <= 100
Accepted
49,263
Submissions
54,082
Seen this question in a real interview before?
Companies
Show Hint 1
Because the vector is sparse, use a data structure that stores the index and value where the element is nonzero.

Average Rating: 4.79 (14 votes)

Premium

Solution

A sparse vector is a vector that has mostly zero values, while a dense vector is a vector where most of the elements are non-zero. It is inefficient to store a sparse vector as a one-dimensional array (Approach 1). Instead, we can store the non-zero values and their corresponding indices in a dictionary, with the index being the key (Approach 2). Alternatively, we can represent elements of a sparse vector as an array of pairs for each non-zero value. Each pair has an integer index and a numerical value (Approach 3).

A related question is LeetCode 311. Sparse Matrix Multiplication.


Approach 1: Non-efficient Array Approach

Intuition

We ignore the sparsity of the array and store the original array.

Algorithm

Complexity Analysis

Let nn be the length of the input array.

  • Time complexity: O(n)O(n) for both constructing the sparse vector and calculating the dot product.

  • Space complexity: O(1)O(1) for constructing the sparse vector as we simply save a reference to the input array and O(1)O(1) for calculating the dot product.


Approach 2: Hash Set

Intuition

Store the non-zero values and their corresponding indices in a dictionary, with the index being the key. Any index that is not present corresponds to a value 0 in the input array.

Algorithm

Complexity Analysis

Let nn be the length of the input array and LL be the number of non-zero elements.

  • Time complexity: O(n)O(n) for creating the Hash Map; O(L)O(L) for calculating the dot product.

  • Space complexity: O(L)O(L) for creating the Hash Map, as we only store elements that are non-zero. O(1)O(1) for calculating the dot product.


Approach 3: Index-Value Pairs

Intuition

We can also represent elements of a sparse vector as a list of <index, value> pairs. We use two pointers to iterate through the two vectors to calculate the dot product.

Algorithm

Complexity Analysis

Let nn be the length of the input array and LL and L2L_{2} be the number of non-zero elements for the two vectors.

  • Time complexity: O(n)O(n) for creating the <index, value> pair for non-zero values; O(L+L2)O(L+L_{2}) for calculating the dot product.

  • Space complexity: O(L)O(L) for creating the <index, value> pairs for non-zero values. O(1)O(1) for calculating the dot product.

Report Article Issue

Comments: 17
BorjaL's avatar
Read More

I would like to propose an improvement in the Hashmap solution. Instead of traversing the hash maps of the first vector, choose the one with minimum length min(v1.keySet().length, v2.keySet().length)

96
Show 8 replies
Reply
Share
Report
dagnyamrutha's avatar
Read More

I got this question at my FB onsite in August 2020. The interviewer did not accept my hashmap solution. He told me that hashing/lookups, while on surface look efficient, for large sparse vectors, hashing function takes up bulk of the computation that we might be better off with the first method. Wihile proposing hashmap/set solutions, take a minute to think about the complexity hashing function.

71
Show 16 replies
Reply
Share
Report
cy_wang's avatar
Read More

Am I the only one didn't get the point of the medium level tag?

31
Show 2 replies
Reply
Share
Report
mp0wr's avatar
Read More

Perf vs Efficiency

Has anyone found an algorithm that is both performant and Facebook-approved?
The "non-efficient array approach" performed best.
JavaScript Map, Object and Set performed horribly.
I did get a "tuple" (array of [index, value]) to perform a little better, 30% slower than array.
Using Array.reduce or switching to the smaller size collection made runtime worse.

// ARRAY
// Runtime: 100 ms, faster than 98.92%
// Memory Usage: 51 MB, less than 95.04%
function SparseVector(nums) {
  return {
    nums,
    dotProduct: function(vec) {
      let d = 0

      for (let i = 0; i < vec.nums.length; i++) {
        if (this.nums[i] && vec.nums[i]) d += this.nums[i] * vec.nums[i]
      }
      return d;
    }
  };
}

// "TUPLE"
// Runtime: 132 ms, faster than 42.89%
// Memory Usage: 53.4 MB, less than 62.50%
class SparseVector {

  constructor(nums) {
    this.nums = [...nums.entries()].filter(el => el[1] !== 0);
  }

  dotProduct(vec) {
    let d = 0;
    for(let [index, value] of vec.nums){
      let num = this.nums.find(el => el[0] === index);
      if(num) d += value * num[1];
    }
    return d;
  }
}

// MAP
// 396 ms, faster than 5.17%
// Memory Usage: 71.3 MB, less than 5.17%
class SparseVector {

  constructor(nums) {
    this.nums = new Map([...nums.entries()].filter(el => el[1] !== 0));
  }

  dotProduct(vec) {
    let d = 0;
    this.nums.forEach((el, i) => {
      if (vec.nums.has(i)) d += vec.nums.get(i) * el;
    });
    return d;
  }
}

// OBJECT
// Runtime: 160 ms
// Memory Usage: 56.7 MB
function SparseVector(nums) {
  return {
    nums: nums.reduce((acc, el, i) => {
      if(el !== 0) acc[i] = el;
      return acc;
    }, {}),
    has: function(i){
      return this.nums.hasOwnProperty(i);
    }, 
    dotProduct: function(vec) {
      let d = 0;
      
      for (let [i, v] of Object.entries(vec.nums)) {
        if(this.has(i)) d += this.nums[i] * v;
      }
      return d;
    }
  };
}


3
Show 1 reply
Reply
Share
Report
dodeja's avatar
Read More

This should be easy.

3
Reply
Share
Report
xiujia_j's avatar
Read More

For approach #1, we could optimize by continuing the loop when either of the array has a 0 (no need to calculate the product)

3
Reply
Share
Report
aehf89's avatar
Read More

I read the comments about FB onsite not accepting the hashmap solution. Could using linked lists be an additional option? I think it's the same time/space as these other solutions, but easier to code.

When you create the spare vector, iterate and generate a linked list of values != 0. Each node tracks its idx and val. That's O(N) time O(L) space to create the vectors.

For dot product, iterate over each linked list with a pointer. If the idx values don't match, move up the pointer with the lower idx value etc. It's O(min(L1, L2)) time O(1) space to calculate dot product. Now you don't have to worry about which linked list is shorter - you just stop when you reach the end of one of them.

My solution came at the bottom of time/space, but posting here anyway:

class VectorNode:
    def __init__(self, idx, val):
        self.idx = idx
        self.val = val
        self.next = None

class SparseVector:
    def __init__(self, nums: List[int]):
        self.list = None
        curr = None

        for idx, val in enumerate(nums):
            if val != 0:
                node = VectorNode(idx, val)
                if not self.list:
                    self.list = node
                    curr = node
                else:
                    curr.next = node
                    curr = node

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        left = self.list
        right = vec.list

        total = 0
        while left and right:
            if left.idx == right.idx:
                total += (left.val * right.val)
                left = left.next
                right = right.next
            elif left.idx < right.idx:
                left = left.next
            else:
                right = right.next

        return total

2
Show 4 replies
Reply
Share
Report
johnjordancog's avatar
Read More

Love the Hashmap way, nice and clean

2
Reply
Share
Report
rishinder's avatar
Read More

The question doesn't make sense. There needs to be some practical use of such an approach. There's no better/worst solution in normal use case.

0
Reply
Share
Report
thisisds's avatar
Read More


class SparseVector:
    def __init__(self, nums: List[int]):
        # Time: O(M), Space: O(M) where M is the length of the vector
        self.vector =  {}
        for idx, num in enumerate(nums):
            if num!=0:
                self.vector[idx] = num

    # Return the dotProduct of two sparse vectors
    def dotProductNormal(self, vec: 'SparseVector') -> int:
        # Time: O(M)
        prod = 0
        for idx,val in self.vector.items():
            if idx in vec.vector:
                prod += val * vec.vector[idx]
        
        return prod
    
    # Return the dotProduct of two sparse vectors
    # when only one of them is sparse
    def dotProductFollowUp(self, vec: 'SparseVector') -> int:
        # Time: O(min(M,N)) where M and N are length of the two vectors
        prod = 0
        vec1, vec2 = sorted([self,vec],key = lambda x: len(x.vector))
        # iterate through the sparse one, whichever has smaller length
        for idx,val in vec1.vector.items():
            if idx in vec2.vector:
                prod += val * vec2.vector[idx]
        
        return prod
    
    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        # return self.dotProductNormal(vec)
        return self.dotProductFollowUp(vec)

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.